#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@Author  :   JingV
@Version :   1.0
@Contact :   None
@License :   None
@Desc    :   None
'''


class Solution(object):
    def combinationSum(self, candidates, target):
        candidates = sorted(candidates)

        ans = []

        def find(start, use, remain):
            for i in range(start, len(candidates)):
                c = candidates[i]
                if c == remain:
                    ans.append(use + [c])
                if c < remain:
                    find(i, use + [c], remain - c)
                if c > remain:
                    return
        find(0, [], target)

        return ans


def main():
    solution = Solution()
    tests = [([2, 3, 6, 7], 7)]
    for candidates, target in tests:
        print(solution.combinationSum(candidates, target))


if __name__ == "__main__":
    main()
